/*
 * @Author: szx
 * @Date: 2022-02-27 14:37:16
 * @LastEditTime: 2022-02-27 15:08:33
 * @Description:
 * @FilePath: \leetcode\1-99\28\28_2.js
 */
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    const m = haystack.length,
        n = needle.length;
    if (n == 0) return 0;
    // 求next数组
    const next = new Array(n).fill(0);
    let k = 0;
    for (let i = 1; i < n; i++) {
        while (k > 0 && needle[i] != needle[k]) k = next[k - 1];
        if (needle[i] == needle[k]) k++;
        next[i] = k;
    }
    k = 0;
    for (let i = 0; i < m; i++) {
        while (k > 0 && haystack[i] != needle[k]) k = next[k - 1];
        if (haystack[i] == needle[k]) k++;
        if (k == n) return i - k + 1;
    }
    return -1;
};
console.log(strStr('aabaabaaf', 'aabaaf'));
